1. Field
Certain aspects of the present disclosure generally relate to low density parity check codes and, more particularly, to a method for constructing a parity check matrix, encoding and decoding.
2. Background
With the explosive growth in multimedia and broadband services over wired and wireless networks, significant effort has been made to apply highly efficient error correcting coding to data transmission over noisy and impaired channels. Low Density Parity Check (LDPC) codes have emerged as one of the most promising error correcting codes due to their offering of higher speeds with significantly lower complexity by taking advantage of the natural parallelism of LDPC codes. In fact, LDPC coded were the first to allow data transmission close to the theoretical limit, e.g., the Shannon limit.
A Low Density Parity Check (LDPC) codes is an error correcting code that is used to detect and correct errors introduced during transmission over a noisy and impaired channel. A binary LDPC code is a block error-correcting code based on a sparse Parity Check Matrix (PCM) H, i.e. matrix H contains mostly 0's and only a small number of 1's or equivalently H has low density of 1's. An (N, K) LDPC code is a linear block code whose PCM HM×N contains M rows where M=N−K and N columns. A regular (N, K, Wc, Wr) LDPC code is a linear block code for which the PCM HM×N contains exactly Wc1's per column and exactly Wr=WcN/M 1's per row, where the low density constraints implies that Wr<<N and Wc<<M. The code rate is Rate=K/N=1−M/N=1−Wc/Wr. If the number of ones in each row or column is not constant than such codes are called irregular LDPC codes.
An LDPC code can be defined in both matrix form and graphical form. An LDPC code can be graphically defined by a Tanner bipartite graph corresponding to the PCM HM×N. Not only do such graphs provide a complete representation of the code, they also describe the decoding algorithm explained in more detail below. A Tanner bipartite graph is essentially a visual representation of the PCM HM×N. A M×N PCM HM×N defines a code in which the N bits of each codeword satisfy a set of M parity-check constraints. The Tanner graph contains N bit-nodes (also called variable nodes); one for each bit, and M check-nodes (also called parity nodes); one for each of the parity check equations. The check-nodes are connected via edges (also called arcs) to the bit nodes they check. Specifically, a branch connects check-node i to bit-node j if and only if the i-th parity check equation involves the j-th bit, or more succinctly, if and only if Hi,j=1. The graph is said to be bipartite because there are two distinct types of nodes, bit-nodes and check-nodes, and there are no direct connection between any two nodes of the same type.
An LDPC code may also be defined using a generator matrix GN×K. A message (also called dataword) dM×1 comprising M bits is encoded into a codeword as followscN×1=GN×KdK×1 Alternatively, the dataword dM×1 can be encoded into a codeword cN×1 using the PCM HM×N by solving for the constraints specified in the following equationHM×NcN×1=0M×1 An LDPC encoded data stream comprising one or multiple codewords is typically transmitted over a noisy and/or impaired channel. A received word corresponding to a transmitted codeword may be contaminated with errors. An LDPC decoder is used to detect and/or correct the errors. LDPC decoding is based on iterative decoding using a message-passing algorithm as an alternative to an optimal yet highly complex maximum-likelihood decoding. Received words are processed iteratively over a Tanner graph wherein messages are exchanged iteratively between bit nodes and parity nodes until a stopping criterion is satisfied.
Conventional LDPC PCMs are random in nature which leads to fully parallel LDPC encoders and decoders. Fully parallel LDPC decoding means that all the messages to and from parity nodes have to be computed at every iteration in the decoding process. This leads to large complexity, increased power and increased cost. Serializing part of the decoder by sharing a number of parity node processing elements (PNPE) is one option for reducing some of the overhead involved; however, serializing part of the decoder would result in stringent memory requirements to store the messages and in an interconnection complexity bottleneck network, i.e. complex interconnects and multiplexing between Variable Nodes Processing Elements (VNPEs), PNPEs and memory.
Further, if different coding rates are to be supported, then the encoder and decoder become even more complex in terms of memory size and architecture, speed, interconnect and multiplexing complexity.
Therefore, there is a need in the art for a method of high speed multi-rate LDPC encoding and decoding that avoids the drawbacks of the standard LDPC encoding and standard message-passing decoding algorithms.